package simulation;

import java.util.ArrayList;
import java.util.List;


public class SpiralMatrix54 {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        search(0, m - 1, 0, n - 1, result, matrix);
        return result;
    }

    private void search(int x_begin, int x_end, int y_begin, int y_end, List<Integer> result, int[][] matrix) {
        if (x_begin > x_end || y_begin > y_end) {
            return;
        }
        if (x_begin == x_end) {
            for (int i = y_begin; i <= y_end; i++) {
                result.add(matrix[x_begin][i]);
            }
            return;
        }
        if (y_begin == y_end) {
            for (int i = x_begin; i <= x_end; i++) {
                result.add(matrix[i][y_begin]);
            }
            return;
        }

        for (int i = y_begin; i < y_end; i++) {
            result.add(matrix[x_begin][i]);
        }
        for (int i = x_begin; i < x_end; i++) {
            result.add(matrix[i][y_end]);
        }

        for (int i = y_end; i > y_begin; i--) {
            result.add(matrix[x_end][i]);
        }
        for (int i = x_end; i > x_begin; i--) {
            result.add(matrix[i][y_begin]);
        }

        search(x_begin + 1, x_end - 1, y_begin + 1, y_end - 1, result, matrix);
    }

}
